package robotRouting;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import monitor.Neibour;
import monitor.Node;
import monitor.NodeList;

public class NodeRouting {

	/**
	 * @malei transform the undirected graph to tree in order to calculate the
	 *        routing path
	 */

	private int sourceId;
	private int targetId;
	private Node[] nodeArray;

	// private Queue<Integer> queue;
	// private Queue<Integer> treeQueue;
	private ArrayList<Integer> resultList; // Store the reuslt route in reverse
											// order

	private int dist[];
	private int previous[];
	private NodeList nl;

	public NodeRouting(int sourceId, int targetId, NodeList nl) {
		super();
		this.sourceId = sourceId;
		this.targetId = targetId;
		this.nl = nl;
		nodeArray = new Node[10];

		int size = nl.size();

		while (size > 0) {
			Node temp = nl.getNode(size - 1);
			nodeArray[temp.getId()] = temp;
			size--;
		}

		// queue = new LinkedList<Integer>();
		// treeQueue = new LinkedList<Integer>();
		resultList = new ArrayList<Integer>();

	}
	
	public ArrayList<Integer> getResultList() {
		return resultList;
	}

	public void setResultList(ArrayList<Integer> resultList) {
		this.resultList = resultList;
	}

	public void reslutDisplay() {
		System.out.println("RoutePath Display:");

		int size = resultList.size();

		for (int i = 0; i < size; i++) {

			System.out.println(resultList.get(i));

		}

	}

	public boolean findPath() {
		boolean flag=true;
		dijkstra();
		int target = targetId;
		resultList.add(target);
		while (previous[target] != -1) {
			resultList.add(previous[target]);
			target = previous[target];
		}

		if (target != sourceId) {

//			System.out.println("Can not find the path from " + sourceId
//					+ " to " + targetId);
//			System.exit(0);
			flag=false;
			return flag;
		}

//		reslutDisplay();
		return flag;
	}

	// Tree Based approach
	// public void buildTree(int source) {
	//
	// queue.add(source);
	//
	// while (!queue.isEmpty()) {
	// int temp = queue.remove();
	// treeQueue.add(temp);
	//
	// List<Neibour> neighbors = nodeArray[temp].neibours;
	//
	// int num = neighbors.size();
	//
	// while (num > 0) {
	// int n = neighbors.get(num - 1).getId();
	//
	// if (!treeQueue.contains(n) && !queue.contains(n)) {
	// queue.add(n);
	// nodeArray[n].setParent(nodeArray[temp]);
	// }
	// num--;
	//
	// }
	//
	// }
	//
	// }
	//
	// public boolean existPath() {
	// boolean flag = false;
	// Node n = nodeArray[targetId];
	// while (n.getParent() != null) {
	// System.out.println(n.getParent().getId());
	// resultList.add(n.getId());
	// n = n.getParent();
	// }
	//
	// if (n.getId() == sourceId) {
	// flag = true;
	// }
	//
	// return flag;
	//
	// }

	// Dijkstra algorithm

	public void dijkstra() {
		previous = new int[10];
		// dist= new int[10];
		for (int i = 0; i < 10; i++) {

			previous[i] = -1;
			// dist[i]=100;
		}

		// dist[sourceId]=0;

		int size = nl.size();
		while (size > 0) {
			Node tempNode = nl.getNode(size - 1);
			tempNode.setDist(100);
			tempNode.setParent(null);

			if (tempNode.getId() == sourceId) {
				tempNode.setDist(0);
			}
			size--;
		}

		while (nl.size() > 0) {
			Node u = smallestDistanceNode();
			if (u.getDist() == 100)
				break;

			nl.removeNodeId(u.getId());

			List<Neibour> neibours = u.neibours;

			int neibourSize = neibours.size();

			while (neibourSize > 0) {
				int alt = u.getDist() + 1;
				int neiboursId = neibours.get(neibourSize - 1).getId();

				if (alt < nodeArray[neiboursId].getDist()) {
					nodeArray[neiboursId].setDist(alt);
					previous[neiboursId] = u.getId();

				}
				neibourSize--;

			}
		}

		System.out.println("The previous array:");

		for (int i = 0; i < 10; i++) {
			System.out.println(previous[i]);
		}

	}

	public Node smallestDistanceNode() {
		Node n = null;
		int size = nl.size();
		while (size > 0) {
			if (n == null) {
				n = nl.getNode(size - 1);
				size--;
			} else {
				if (n.getDist() > nl.getNode(size - 1).getDist()) {
					n = nl.getNode(size - 1);
				}
				size--;

			}

		}

		return n;
	}



	public int findNode(Node n, NodeList nl) {
		int id = n.getId();

		int size = nl.size();

		while (size > 0) {
			if (id == nl.getNode(size - 1).getId())
				return size;

			size--;
		}

		return -1;

	}

	public static void main(String[] args) {

		Node n8 = new Node(8, 1);
		Neibour ng4 = new Neibour(4);
		
		NodeList nl = new NodeList();

		
		
		
		
		Node n2 = new Node(2, 1);
		Node n3 = new Node(3, 1);
		
		
		
		
		Neibour ng2 = new Neibour(2);

		Neibour ng3 = new Neibour(3);
		
		n3.addNeibour(ng2);
		n2.addNeibour(ng3);

		nl.addNode(n8);
		nl.addNode(n2);
		nl.addNode(n3);
		
//		Node n4 = new Node(4, 1);
//		Node n5 = new Node(5, 1);
//
//		Neibour ng1 = new Neibour(1);
//		Neibour ng2 = new Neibour(2);
//		Neibour ng3 = new Neibour(3);
//		Neibour ng4 = new Neibour(4);
//		Neibour ng5 = new Neibour(5);
//
//		n1.addNeibour(ng2);
//
//		n2.addNeibour(ng1);
//		n2.addNeibour(ng3);
//		n2.addNeibour(ng4);
//
//		n3.addNeibour(ng2);
//
//		n4.addNeibour(ng3);
//		n4.addNeibour(ng5);
//
//		n5.addNeibour(ng4);
//
//		NodeList nl = new NodeList();
//
//		nl.addNode(n1);
//		nl.addNode(n3);
//		nl.addNode(n2);
//		nl.addNode(n4);
//		nl.addNode(n5);

		// System.out.println(nl.size());

		// int temp=nl.size();
		//
		// while(temp>0){
		// System.out.println(nl.getNode(temp-1).getId());
		//
		// temp--;
		//
		// }

		NodeRouting nr = new NodeRouting(2, 3, nl);

		// nr.buildTree(1);
		// nr.dijkstra();
		nr.findPath();

		// Node n = nr.nodeArray[4];
		// while (n.getParent() != null) {
		// System.out.println(n.getParent().getId());
		// n = n.getParent();
		// }

	}

}
